package Top200;

/**
 * @author zhangmin
 * @create 2022-02-18 9:55
 * 记录两边的最大值
 */
public class trap42 {
    public int trap(int[] height) {
        int n=height.length;
        int[] left=new int[n];
        int[] right=new int[n];
        left[0]=height[0];
        right[n-1]=height[n-1];
        for (int i = 1; i < n; i++) {
            left[i]=Math.max(left[i-1],height[i]);
            right[n-i-1]=Math.max(right[n-i],height[n-i-1]);
        }
        int res=0;
        for (int i = 1; i < n-1; i++) {
            res+=Math.min(left[i],right[i])-height[i];
        }
        return res;
    }
}
